package org.chnxi.study.datastructrues.tree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Objects;

/**
 * 二拆排序树
 */
public class BinarySortTreeDemo {

    public static void main(String[] args) {

        System.out.println("创建二拆排序树");
        int[] arr = {7,3,10,12,5,1,9,2};

        BinarySortTree<BSTEntity> tree = new BinarySortTree<>();

        for (int idx : arr){
            tree.add(new BSTreeNode<BSTEntity>(new BSTEntity(idx , "name-"+idx)));
        }

        tree.printByInfixOrder();
        System.out.println("==============================");
        System.out.println("删除叶子节点：");
        BinarySortTree<BSTEntity> tree1 = new BinarySortTree<>();
        for (int idx : arr){
            tree1.add(new BSTreeNode<BSTEntity>(new BSTEntity(idx , "name-"+idx)));
        }
        System.out.println("删除前：");
        tree1.printByInfixOrder();
        tree1.delNode(new BSTEntity(2 , "name-2"));
        System.out.println("删除后：");
        tree1.printByInfixOrder();

        System.out.println("==============================");
        System.out.println("删除只有一个子节点的节点：");
        BinarySortTree<BSTEntity> tree2 = new BinarySortTree<>();
        for (int idx : arr){
            tree2.add(new BSTreeNode<BSTEntity>(new BSTEntity(idx , "name-"+idx)));
        }
        System.out.println("删除前：");
        tree2.printByInfixOrder();
        tree2.delNode(new BSTEntity(1 , "name-2"));
        System.out.println("删除后：");
        tree2.printByInfixOrder();

        System.out.println("==============================");
        System.out.println("删除只有一个子节点的节点：");
        BinarySortTree<BSTEntity> tree3 = new BinarySortTree<>();
        for (int idx : arr){
            tree3.add(new BSTreeNode<BSTEntity>(new BSTEntity(idx , "name-"+idx)));
        }
        System.out.println("删除前：");
        tree3.printByInfixOrder();
        tree3.delNode(new BSTEntity(10 , "name-2"));
        System.out.println("删除后：");
        tree3.printByInfixOrder();

    }

}

class BinarySortTree<E extends Comparable<E>>{

    private BSTreeNode<E> root;

    /**
     * 查找节点
     * @param e
     * @return
     */
    public BSTreeNode<E> search(E e){
        if(root == null){
            return null;
        }
        return root.search(e);
    }

    /**
     * 查找指定节点的父节点
     * @param e
     * @return
     */
    public BSTreeNode<E> searchParent(E e){
        if(root == null){
            return null;
        }
        return root.searchParent(e);
    }

    /**
     * 实现功能：
     *   1. 找到最小节点的值
     *   2. 删除该节点
     * @param node 传入的节点（当做二叉树排序节点的根节点）
     * @return 返回以node为根节点的二叉排序树的最小节点的值
     */
    public E delRightTreeMin(BSTreeNode<E> node){

        BSTreeNode<E> target = node;
        //循环查找左子节点，就会找到最小值
        while(target.left != null){
            target = target.left;
        }
        //删除最小节点
        delNode(target.e);
        return target.e;
    }

    /**
     * 删除节点
     * @param e 要删除节点的值
     */
    public void delNode(E e){
        if(root == null){
            return;
        }
        //先找到该节点
        BSTreeNode<E> node = search(e);
        if(node == null){ //要删除的节点未找到
            return;
        }

        //目标节点是根，且没有左右子节点
        if(root.left == null && root.right == null){
            root = null;
            return;
        }

        //查找删除节点的父节点
        BSTreeNode<E> parent = searchParent(e);

        //如果要删除的节点是叶子节点
        if(node.left == null && node.right == null){
            //判断node是parent的左子节点还是右子节点
            if(parent.left != null && parent.left.e.equals(e)){ //删除左子节点
                parent.left = null;
            }else if(parent.right != null && parent.right.e.equals(e)){ //删除右子节点
                parent.right = null;
            }
        }else if(node.left != null && node.right != null){ //删除的节点有两颗子树
            E mine = delRightTreeMin(node.right);
            node.e = mine;
        }else{ //剩余只有一个子树的情况
            if(node.left != null){
                if(parent != null){
                    if(parent.left.e.equals(e)){
                        parent.left = node.left;
                    }else{
                        parent.right = node.left;
                    }
                }else{
                    root = node.left;
                }
            }else{
                if(parent != null){
                    if(parent.left.e.equals(e)){
                        parent.left = node.right;
                    }else{
                        parent.right = node.right;
                    }
                }else{
                    root = node.right;
                }
            }

        }

    }

    /**
     * 添加子节点
     * @param node
     */
    public void add(BSTreeNode<E> node){
        if(root == null){
            root = node;
        }else{
            root.add(node);
        }
    }

    /**
     * 使用中序遍历打印
     */
    public void printByInfixOrder(){
        if(root != null){
            root.printByInfixOrder();
        }
    }

}

class BSTreeNode<E extends Comparable<E>> {

    E e;

    BSTreeNode<E> left;

    BSTreeNode<E> right;

    public BSTreeNode(E e){
        this.e = e;
    }

    /**
     * 查找节点
     * @param e 希望找到的节点的值
     * @return 找到返回节点，否则返回null
     */
    public BSTreeNode<E> search(E e){
        int diff = this.e.compareTo(e);
        if(diff == 0){ //返回当前节点
            return this;
        } else if(diff > 0){ //小于当前节点，从左子树查找
            if(this.left != null){
                return this.left.search(e);
            }
        }else{ //大于当前节点，从右子树查找
            if(this.right != null){
                return this.right.search(e);
            }
        }
        return null;
    }

    /**
     * 查找目标节点的父节点
     * @param e 要查找节点的值
     * @return 返回目标节点的父节点，否则返回null
     */
    public BSTreeNode<E> searchParent(E e){
        if((this.left != null && this.left.e.equals(e) ) ||
                (this.right != null && this.right.e.equals(e))){
            return this;
        } else {
            int diff = this.e.compareTo(e);
            if(diff > 0 && this.left != null){ //从左子树进行查找
                return this.left.searchParent(e);
            }else if(diff <= 0 && this.right != null){ //从右子树递归查找
                return this.right.searchParent(e);
            }else{
                return null;
            }
        }
    }

    /**
     * 添加节点
     * @param node
     */
    public void add(BSTreeNode<E> node){
        if(node == null){
            return;
        }
        int diff = this.e.compareTo(node.e);
        if(diff < 0){
            if(this.right == null){
                this.right = node;
            }else{
                this.right.add(node); //递归向右子树添加
            }
        }else{
            if(this.left == null){
                this.left = node;
            }else{
                this.left.add(node); //递归向左子树添加
            }
        }
    }

    /**
     * 使用中序遍历打印
     */
    public void printByInfixOrder(){
        if(this.left != null){
            this.left.printByInfixOrder();
        }
        System.out.println(this);
        if(this.right != null){
            this.right.printByInfixOrder();
        }
    }

    @Override
    public String toString() {
        return "BSTreeNode{e=" + e + "}";
    }
}

@Data
@AllArgsConstructor
@NoArgsConstructor
class BSTEntity implements Comparable<BSTEntity>{

    private int id;

    private String name;

    @Override
    public int compareTo(BSTEntity o) {
        return this.id - o.id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        BSTEntity bstEntity = (BSTEntity) o;
        return id == bstEntity.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}